#define elif else if
#include<bits/stdc++.h>
#include"heap.cpp"
using namespace std;
int* D;
struct Comp
{
	static bool prior(int a, int b)
	{
		//以前文最大堆为例，传入两个E类对象a、b，若对于某个属性a比b大则直接返回
		//此时比较D值，且顺序是从大到小
		return D[a] < D[b];
	}
};
int main()
{

	int n, e, start, end;
	while (cin >> n >> e >> start >> end) {//n个结点，e条边
		D = new int[n];
		int* pre = new int[n];
		bool* visited = new bool[n];
		for (int i = 0; i < n; i++)
		{
			D[i] = INT_MAX;
			pre[i] = INT_MAX;
			visited[i] = false;
		}
		D[start] = 0;
		heap<int, Comp>minheap;
		minheap.insert(start);
		int** input = new int* [e];
		for (int j = 0; j < e; j++)
			input[j] = new int[2];//初始化输入
		vector< vector<int> >edge;//设置结点对应边数组
		for (int tmp = 0; tmp < n; tmp++)
		{
			edge.push_back(vector<int>());
			for (int tmp2 = 0; tmp2 < n; tmp2++)
			{
				edge[tmp].push_back(INT_MAX);
			}

		}
		for (int j = 0; j < e; j++)
		{
			int weight = 0;
			cin >> input[j][0] >> input[j][1] >> weight;
			edge[input[j][0]][input[j][1]] = weight;
			//每条边的出点和入点以及权重
		}
		for (int sign = 0; sign < n - 1; sign++)
		{
			int ss = minheap.removefirst();
			while (visited[ss])
			{
				ss = minheap.removefirst();
			}
			visited[ss] = true;
			for (int tmp = 0; tmp < n; tmp++)
			{
				if (edge[ss][tmp] != INT_MAX && D[tmp] == INT_MAX)
				{
					D[tmp] = D[ss] + edge[ss][tmp];
					pre[tmp] = ss;
					minheap.insert(tmp);
				}

				elif(D[tmp] != INT_MAX && edge[ss][tmp] != INT_MAX && (D[ss] + edge[ss][tmp] < D[tmp]))
				{
					D[tmp] = D[ss] + edge[ss][tmp];
					pre[tmp] = ss;
					minheap.insert(tmp);
				}
				elif(edge[ss][tmp] == INT_MAX)continue;

			}

		}
		for (int o = 0; o < n; o++)cout << D[o] << " "; cout << endl;
		while (end != start) { cout << end << "<-"; end = pre[end]; }cout << start << endl;
	}
}
//测试数据：第一行为点数、边数、出发点和目的点
//以下数据可直接去除注释复制粘贴使用
//其余每行为各点之间的边及其权重
//warning：出发点和目的点的输入需要其之间有通路
// 5 7 0 4
// 	0 1 10
// 	0 2 3
// 	2 1 2
// 	0 3 20
// 	1 3 5
// 	3 4 11
// 	2 4 15	